package com.fengye.algorithms.leecode.mianshi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有一个整数矩阵land表示一片土地，矩阵每个点的值代表对应地点的海拔高度。若值为0则表示水域。
 * 由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 * 示例：
 * 输入：
 * [ [0,2,1,0],
 *  [0,1,0,1],
 *  [1,1,0,1],
 *  [0,1,0,1] ]
 * 输出： [1,2,4]
 * 提示：0 < len(land) <= 1000 && 0 < len(land[i]) <= 1000
 * @Author fengye
 * @Date 2023/3/14 10:06
 **/
public class PandSizeMain {
    public static void main(String[] args) {
        int[][] land = {{0,2,1,0},{0,1,0,1},{1,1,0,1},{0,1,0,1}};
        Arrays.stream(new PandSizeMain().pondSizes(land)).forEach(System.out::println);
    }

    public int[] pondSizes(int[][] land) {
        int count = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<land.length;i++) {
            for(int j=0;j<land[0].length;j++) {
                if(land[i][j] == 0) {
                    count = countArea(land, i, j);
                    list.add(count);
                }
            }
        }
        int[] result = new int[list.size()];
        for(int i=0;i<list.size(); i++) {
            result[i] = list.get(i);
        }
        Arrays.sort(result);
        return result;
    }

    public int countArea(int[][] land, int i, int j) {
        if(i<0 || i>= land.length || j<0 || j>=land[0].length ) {
            return 0;
        }

        if(land[i][j] != 0) {
            return 0;
        }

        // 标记已经算过了
        land[i][j] = -1;
        int count = 1;
        int[][] visited = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
        for(int v=0;v<visited.length;v++) {
            count += countArea(land, i+visited[v][0], j+visited[v][1]);
        }
        return count;
    }
}
